Schnelle Multiplikation 8Bit auf 16Bit

Thema: Multiplikation mittels Umformung einer Binomischen Formel und Nutzung von Quadrattabellen zur Geschwindigkeitsverbesserung!

Die Idee ist super, es geht aber noch besser... statt die 1. Binomische Formel zu nutzen nimmt man einfach die 2. Binomische Formel! Zunächst ersetzen wir x durch b - das sieht dann mathematisch exakt aus. Die 2. Binomische Formel lautet: (a-b)²=a²+b²-2ab -> 2ab=a²+b²- (a-b)² -> ab=a²/2 + b²/2 - (a-b)²/2 Keine Zahl, die wir als Quadrat ablesen müssen geht nun über 16-Bit - übrigens teilen wir auch gar nicht durch 2, sondern passen die Tabelle einfach an und legen in der Tabelle nicht das Quadrat ab, sondern die Hälfte des Quadrates....

Syntax: a mal b soll ausgerechnet werden, a und b sind max. 8 Bit groß. Zunächst wird der Betrag von a-b gebildet. Dann in der Tabelle die halben Quadrate für a, b und Betrag a-b ablesen, jeweils addieren bzw. subtrahieren... fertig. Den Code dafür baue ich jetzt und stelle ihn hier rein...

LG Peter

... aus Spaß habe ich mir auch für diesen Zweck die 3. Binomische Formel angeschaut: (a+b)(a-b) = a²-b² --> geht auch! Umgeformt (ich verschone euch mal mit der Rechnung) erhält man folgendes: ab = ((a+b)/2)²- ((a-b)/2)² --> sieht erstmal komisch aus, ist aber vielleicht noch schneller:

Addition von a und b, teilen durch 2, dann das Quadrat aus der Tabelle raussuchen. Subtraktion b von a, teilen durch 2, dann das Quadrat aus der Tabelle raussuchen. Beide Werte voneinander subtrahieren, das wars.... ... allerdings teilt man vor dem quadrieren durch 2 und bekommt einen zu großen Rundungsfehler. Teilt man nach dem quadrieren durch 4 (was auch ginge), müsste man wieder über die 32 Bit Tabelle gehen.... a*b = (a+b)²/4 - (a-b)²/4

Guten Morgen Erhard, ich habe das jetzt nicht ganz genau ausgerechnet, aber bleibt man bei der 2. Binomischen Formel, dann enthält die Tabelle alle schon halbierten Quadratergebnisse der 256 Zahlen. Man braucht dann tatsächlich 256 Bytes für den Low-Wert und nochmal 256 Bytes für den High-Wert, also ein halbe kB. Mit schlauer Codierung kommt man sicherlich auch deutlich unter 512 Bytes, das würde aber wieder etwas Zeit kosten... LG Peter

... und hier der Code: Insgesamt wohl noch schneller. Alle diese schnelle Varianten haben neben des etwas erhöhten Speicherbedarfes einen weiteren Nachteil: Man teilt die Quadrate ja durch 2 und bekommt somit automatisch kleinere Rundungsfehler!

a           .by 00      
b           .by 00      
c           .by 00,00       

temp1       .by 00,00       ;Zwischenspeicher1
temp2       .by 00,00       ;Zwischenspeicher2

            ;.... schnelle 8Bit auf 16 Bit-Multiplikation ......
            ; die 2. Binomische Formel lautet:
            ; (a-b)²=a²+b²-2a*b -> 2*a*b=a²+b²-(a-b)² 
            ; -> a*b=a²/2+b²/2-(a-b)²/2 = c

            ; Eingabe als Beispiel für a und b: 11 * 123 = 1353

            lda #11
            sta a
            lda #123
            sta b

            ; Start Routine für a * b = c
            ; Betrag von a-b bilden
            sec
            lda a
            sbc b
            bcs weiter
            sbc #0
            eor #$ff
weiter
            ; ab hier die Quadrate/2 holen und entsprechend die Summanden bilden
            tax     
            lda quadratlow,x
            sta temp1
            lda quadrathi,x
            sta temp1+1
            clc
            ldx a
            lda quadratlow,x
            ldx b
            adc quadratlow,x
            sta temp2
            lda quadrathi,x
            ldx a
            adc quadrathi,x
            sec
            sbc temp1+1
            sta c+1
            lda temp2
            sbc temp1
            sta c

            ;....................... Routine Ende ..........


quadratlow
     .byte   0,  1,  2,  5,  8, 13, 18, 25, 32, 41, 50, 61, 72, 85, 98,113
    .byte 128,145,162,181,200,221,242,  9, 32, 57, 82,109,136,165,194,225
     .byte   0, 33, 66,101,136,173,210,249, 32, 73,114,157,200,245, 34, 81
      .byte 128,177,226, 21, 72,125,178,233, 32, 89,146,205,  8, 69,130,193
     .byte   0, 65,130,197,  8, 77,146,217, 32,105,178,253, 72,149,226, 49
  .byte 128,209, 34,117,200, 29,114,201, 32,121,210, 45,136,229, 66,161
  .byte   0, 97,194, 37,136,237, 82,185, 32,137,242, 93,200, 53,162, 17
  .byte 128,241, 98,213, 72,189, 50,169, 32,153, 18,141,  8,133,  2,129
  .byte   0,129,  2,133,  8,141, 18,153, 32,169, 50,189, 72,213, 98,241
  .byte 128, 17,162, 53,200, 93,242,137, 32,185, 82,237,136, 37,194, 97
  .byte   0,161, 66,229,136, 45,210,121, 32,201,114, 29,200,117, 34,209
  .byte 128, 49,226,149, 72,253,178,105, 32,217,146, 77,  8,197,130, 65
  .byte   0,193,130, 69,  8,205,146, 89, 32,233,178,125, 72, 21,226,177
  .byte 128, 81, 34,245,200,157,114, 73, 32,249,210,173,136,101, 66, 33
  .byte   0,225,194,165,136,109, 82, 57, 32,  9,242,221,200,181,162,145
  .byte 128,113, 98, 85, 72, 61, 50, 41, 32, 25, 18, 13,  8,  5,  2,  1

quadrathi
  .byte   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
  .byte   0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  1,  1
  .byte   2,  2,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  4,  4
  .byte   4,  4,  4,  5,  5,  5,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7
  .byte   8,  8,  8,  8,  9,  9,  9,  9, 10, 10, 10, 10, 11, 11, 11, 12
  .byte  12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 17, 17
  .byte  18, 18, 18, 19, 19, 19, 20, 20, 21, 21, 21, 22, 22, 23, 23, 24
  .byte  24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30, 31, 31
  .byte  32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 37, 37, 38, 38, 39, 39
  .byte  40, 41, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49
  .byte  50, 50, 51, 51, 52, 53, 53, 54, 55, 55, 56, 57, 57, 58, 59, 59
  .byte  60, 61, 61, 62, 63, 63, 64, 65, 66, 66, 67, 68, 69, 69, 70, 71
  .byte  72, 72, 73, 74, 75, 75, 76, 77, 78, 78, 79, 80, 81, 82, 82, 83
  .byte  84, 85, 86, 86, 87, 88, 89, 90, 91, 91, 92, 93, 94, 95, 96, 97
  .byte  98, 98, 99,100,101,102,103,104,105,106,106,107,108,109,110,111
  .byte 112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127

... also tatsächlich habe ich auch schon daran gedacht. Die Genauigkeit ist dann etwas besser und es noch weitere Vorteile: Durch eine normalisierte Tabelle, würde man ganz praktisch auch Wurzeln ziehen können...